package com.zlk.algorithm.algorithm.dynamicPlan.knapsack073;

import java.util.ArrayList;

// 非负数组前k个最小的子序列累加和
// 给定一个数组nums，含有n个数字，都是非负数
// 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
// 子序列是包含空集的
// 1 <= n <= 10^5
// 1 <= nums[i] <= 10^6
// 1 <= k <= 10^5
// 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了
// 对数器验证
public class Code06_TopKMinimumSubsequenceSum {

    // 暴力方法
    // 为了验证
    public static int[] topKSum1(int[] nums, int k) {
        ArrayList<Integer> allSubsequences = new ArrayList<>();
        f1(nums, 0, 0, allSubsequences);
        allSubsequences.sort((a, b) -> a.compareTo(b));
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = allSubsequences.get(i);
        }
        return ans;
    }

    // 暴力方法
    // 得到所有子序列的和
    public static void f1(int[] nums, int index, int sum, ArrayList<Integer> ans) {
        if (index == nums.length) {
            ans.add(sum);
        } else {
            f1(nums, index + 1, sum, ans);
            f1(nums, index + 1, sum + nums[index], ans);
        }
    }

    // 01背包来实现
    //给定一个正数k，返回所有子序列中累加和最小的前k个累加和
    // 这种方法此时不是最优解
    // 因为n很大，数值也很大，那么可能的累加和就更大
    // 时间复杂度太差
    //dp[i][j]  0到i位置 累加和为j  的个数
    //dp[i][j] dp[i-1][j]+dp[i-1][j-nums[i]]
    public static int[] topKSum2(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        int[] dp = new int[sum+1];
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            for (int j = sum; j >=num ; j--) {
                dp[j] +=dp[j-num];
            }
        }
        int index = 0;
        int[] ans = new int[k];
        for (int i = 0; i <= sum&index<k; i++) {
            for (int j = 0; j < dp[i]&&index<k; j++) {
                ans[index++] = j;
            }
        }
        return ans;
    }


}
